💎 Fibonacci Gems Max Heap

Organize precious gems with Fibonacci-inspired sizes using Max Heap.

💎 The Treasure Hunter's Challenge

🎯 The Quest:

A treasure hunter organizes gems with sizes following a modified Fibonacci pattern, starting with 2 and 3 carats instead of the traditional 0 and 1.

📋 Requirements:

  • First gem: 2 carats, Second gem: 3 carats
  • Each subsequent gem: sum of previous two gems
  • Store gems in a Max Heap (largest always at top)
  • Display heap after each insertion
  • Output format: "Insert : "

Problem Specifications

  • Input: Single integer n (1 ≤ n ≤ 10) - number of gems
  • Fibonacci Pattern: F(1) = 2, F(2) = 3, F(i) = F(i-1) + F(i-2)
  • Output: After each insertion, display "Insert X: heap_contents"

Fibonacci Gem Sequence (starting 2, 3)

2 3 5 8 13 21 34 55

Formula: F(n) = F(n-1) + F(n-2), where F(1)=2, F(2)=3

Example: n = 5

Insert 2: 2
Insert 3: 3 2
Insert 5: 5 2 3
Insert 8: 8 5 3 2
Insert 13: 13 8 3 2 5

🔄 Fibonacci Pattern & Max Heap

Modified Fibonacci Sequence

  1. Start with F(1) = 2 and F(2) = 3 (instead of 0, 1)
  2. For n ≥ 3: F(n) = F(n-1) + F(n-2)
  3. Generate first n terms of this sequence
  4. Insert each term into Max Heap as it's generated

Max Heap Operations

  1. Start with empty Max Heap
  2. For each Fibonacci gem size:
    • Insert gem into heap
    • Heapify-up to maintain max heap property (parent ≥ children)
    • Display current heap state
  3. Output format: "Insert X: a b c ..." (space-separated)

Time Complexity

O(n log n)
n insertions, each O(log n)

Space Complexity

O(n)
Storing n gems in heap

Why Max Heap?

The treasure hunter wants the most valuable (largest) gem always accessible at the top. Max Heap ensures:

  • O(1) access to the largest gem (root)
  • Efficient insertions in O(log n) time
  • Maintains ordering automatically through heapify operations

🔍 Step-by-Step Gem Insertion

Ready. Use controls below to start demo.

Max Heap State

Insertion Log

No insertions yet
Click Start to run demo

Progress Tracker

1. Initialize empty Max Heap
2. Generate next Fibonacci gem size
3. Insert gem into heap
4. Heapify-up to maintain property
5. Display heap state
6. Repeat for all gems

🎮 Build Your Gem Collection

Enter n and press Generate Collection

Test Cases

Sample Input 1
n = 5
Expected Output:
Insert 2: 2
Insert 3: 3 2
Insert 5: 5 2 3
Insert 8: 8 5 3 2
Insert 13: 13 8 3 2 5
Sample Input 2
n = 3
Expected Output:
Insert 2: 2
Insert 3: 3 2
Insert 5: 5 2 3
Minimal Case
n = 1
Expected: Insert 2: 2

📊 Analysis & Insights

Time

O(n log n)

n insertions × O(log n) heapify

Space

O(n)

Storing n gem sizes

Detailed Complexity

  • Fibonacci Generation: O(n) - linear calculation with previous two values
  • Heap Insertion: O(log n) per gem due to heapify-up
  • Total Insertions: n gems → O(n log n)
  • Overall: O(n) + O(n log n) = O(n log n)

Fibonacci Pattern Analysis

Modified Fibonacci starting with 2, 3:

  • F(1) = 2, F(2) = 3
  • F(3) = 2 + 3 = 5
  • F(4) = 3 + 5 = 8
  • F(5) = 5 + 8 = 13
  • F(6) = 8 + 13 = 21
  • Growth rate: Approximately φ^n where φ ≈ 1.618 (golden ratio)

Max Heap Properties

  • Complete Binary Tree: All levels filled except possibly last
  • Max Heap Property: Every parent ≥ children
  • Root Element: Always the largest value
  • Array Representation: Parent at i, children at 2i+1, 2i+2
  • Heapify-Up: Bubble newly inserted element up until property restored

Real-World Applications

  • Priority Queues: Task scheduling, event handling
  • Resource Management: Allocating to highest priority requests
  • Game Development: Managing enemy spawn priorities
  • Data Streaming: Finding top-K elements efficiently
  • Network Routing: Selecting optimal paths